package com.code.leetcode._202503;


/**正则表达式匹配
 * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * **/
public class ZhengZeExpressing {
    /*动态规划
    * p有三种字符  普通字符  .匹配任意字符   * 跟前面一个字符搭配，可以出现多次
    * */
    public static boolean isMatch(String ss,String pp){
        //往原字符头部插入空格，这样得到char数组是从1开始，而且可以使得f[0][0] = true,可以讲true这个结果滚动下去
        int n = ss.length(),m= pp.length();
        ss = " "+ss;
        pp = " "+pp;
        //f(i,j) 代表考虑s中的1-i字符和p中的1-j字符是否匹配
        char[] s = ss.toCharArray(),p = pp.toCharArray();
        boolean[][] f = new boolean[n+1][m+1];
        f[0][0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <=m ; j++) {
                //如果如果下一个字符是"*"，则代表当前字符不能被单独使用，跳过
                if (j+1 <=m&&p[j+1] == '*' &&p[j]!= '*') continue;
                //对应了p[j] 为普通字符和’.‘的两种情况
                if (i-1 >= 0 && p[j] !='*'){
                    f[i][j] = f[i-1][j-1] && (s[i]==p[j] || p[j] =='.');
                }else if (p[j]=='*'){
                    //对应了p[j]为*的情况
                    f[i][j] = (j-2 >=0&&f[i][j-2])||(i-1>=0&&f[i-1][j]&&(s[i]==p[j-1] || p[j-1]=='.'));
                }
            }
        }
        return f[n][m];
    }

    /***
     *
     */
    public boolean isMatch1(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }

    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }

}
